1. Technical Field
The present invention relates to circuit design and verification of circuits. More particularly, the present invention relates to interconnection circuit modeling. Still more particularly, the present invention relates to model reduction for interconnection circuit modeling and analysis.
2. Description of Related Art
Interconnect effects are critically important in the design and verification of integrated circuits. On-chip interconnects are typically modeled by linear resistive (R) and capacitive (C) elements. In some cases, very few global nets may also include inductive (L) elements. With the scaling of the Back-End-Of-the-Line (BEOL) interconnect processes, the effect of interconnect on circuit performance continues to increase. In case of global nets (i.e., nets connecting one macro to another macro), the interconnect delay can typically be much greater than the logic delay. Even among nets within a macro, the interconnect delay can constitute a significant portion of the path delay (i.e., typically up to 25%).
Interconnect modeling is typically performed through a layout-based extraction procedure. Extracted data from a microprocessor may require 2-4 gigabytes of storage. Given the massive amount of data generated by parasitic extractors, it is typically not feasible to perform circuit analysis without use of model reduction or other interconnect pruning techniques.
Model reduction takes an original linear circuit and reduces it to a much smaller linear representation while maintaining much of the circuit performance. Model reduction has been an area of considerable research over the last several years, with much of the work originating from Asymptotic Waveform Evaluation (AWE), disclosed by Pillage and Rohrer in "Asymptotic Waveform Evaluation for Timing Analysis", IEEE Trans. Computer Aided Design, 9(4):352-366, Apr. 1990. AWE computes the moments of the original circuit and then matches these moments to a reduced-order transfer function using Pade approximation. Along with the moment matching techniques, AWE, and later RICE, disclosed by Ratzlaff and Pillage in "RICE: Rapid Interconnect Circuit Evaluator using Asymptotic Waveform Evaluation", IEEE Transactions on Computer Aided Design, pp. 763-776, June 1994, proposed an efficient way of computing the circuit moments by repeated DC solutions. Typically, RC circuits can be modeled by a handful of moments. RLC and PEEC circuits require much larger numbers of moments, though they are typically not used to model on-chip interconnects. The repeated DC solutions used to compute moments causes the accuracy of the moments to decrease as the number of moments increase. Several techniques, notably using Krylov-subspace methods, were developed to increase the accuracy of the model reduction procedure, as disclosed by Feldmann and Fruend, "Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm", Proceedings of ACM/IEEE Design Automation Conference, pp. 474-479, 1995; Kerns, Wemple and Wang, "Stable and Efficient Reduction of Substrate model networks using Congruence Transforms", Proceedings of IEEE International Conference on Computer Aided Design, pp. 207-214, November 1995; Gallivan, Grimme and Van Dooren, "Asymptotic Waveform Evaluation via a Lanczos Method", Applied Mathematics Letters, 7(5):75-80, 1994; Silveria, Kamon, Elfadel and White, "Coupled circuit-interconnect analysis using Arnoldi-based model order reduction", IEEE Transactions on Computer Aided Design, 1995. Krylov-subspace methods can match a much higher number of implicit moments yielding much higher accuracy. These techniques are also more suitable for analyzing the frequency response of linearized analog circuits. Block Krylov-subspace methods were developed to handle multi-port circuits; however, these methods typically work well only when the number of ports is less than ten. Krylov-subspace techniques match the original circuit to a set of state equations that describe the reduced circuit. However, the reduced order state equations may not be passive or realizable. Techniques disclosed in Odabasioglu, Celik and Pileggi, "PRIMA: Passive Reduced-Order Interconnect Macromodeling Algorithm,"IEEE Transactions on CAD, pp. 645-654, August 1998; and Kerns et al., "Stable and Efficient Reduction of Substrate model networks using Congruence Transforms", extend the Krylov-subspace methods to guarantee the passivity of the reduced order state equations. However, these methods do not guarantee the realizability (i.e., modeling reduced order state equations by linear, passive circuit elements) of the reduced circuit equations. Realizability of the reduced order models has been shown only for single port circuits, as discussed in O'Brien and Savarino, "Modeling the driving-point characteristics of resistive interconnect for accurate delay estimation", Proceedings of IEEE International Conference on Computer Aided Design, pp. 512-515, November 1989; and Freund and Feldmann, "Reduced-Order Modeling of Large Passive Linear Circuits by Means of the SyPVL Algorithm,"Proceedings of IEEE Conference on Computed Aided Design, November 1996.
Realizable model reduction is particularly useful in interconnect analysis. In a typical design methodology, various circuit analysis and verification procedures (e.g., static timing, dynamic simulation, noise analysis, circuit checking, power analysis, etc.) are performed on the extracted parasitic data. If the model reduction of the parasitic data is not realizable, it produces reduced transfer functions or reduced state equations and not reduced RC circuits. Hence, all downstream circuit simulators and associated programs have to be modified to handle reduced order equations. Realizable reduced models are even more useful when both linear and nonlinear parts of the circuit have to be analyzed together. Furthermore, several circuit analysis programs (like circuit checking) only work if the input is in the form of an RC circuit.
Apart from realizability, another significant problem in interconnect analysis is the large number of ports. For example, RC circuits originating from clock and power distribution networks may have hundreds of ports. In some cases, especially for linear analysis, the prior art approximates these networks with single port networks having linear terminations at the other ports. This approximation to single port networks has the disadvantages of causing a loss in accuracy and difficulty in predicting when the approximation works well. For on-chip interconnects, addressing the need for an increase in the number of ports is often more important than increasing the order of the approximation. On-chip interconnects do not require large numbers of moments to produce accurate results. However, they typically do have large numbers of ports. Model reduction of these circuits yields a dense reduced order model which can be prohibitively expensive to analyze using downstream circuit analysis tools. The matrix factorization of a dense matrix is order 0(n.sup.3) , whereas the matrix factorization of a sparse matrix is order 0(n.sup.1.5). For the case of circuits with large numbers of ports, the simulation with reduction may often take longer than simulation without reduction.